package pers.qianyu.month_202012.date_20201229;

import org.junit.*;

import java.util.*;

/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * @author mizzle rain
 * @date 2020年12月29日19:54:34
 */
public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        Deque<Integer> q = new LinkedList<>();
        int[] res = new int[len - k + 1];
        int t = 0;
        for (int i = 0; i < len; i++) {
            if (i >= k && nums[i - k] == q.getFirst()) q.pollFirst();
            while (!q.isEmpty() && q.getLast() < nums[i]) q.pollLast();
            q.addLast(nums[i]);
            if (i >= k - 1) {
                res[t++] = q.getFirst();
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = new MaxSlidingWindow().maxSlidingWindow(nums, k);
        Assert.assertArrayEquals(result, new int[]{3, 3, 5, 5, 6, 7});
    }

    @Test
    public void test2() {
        int[] nums = {7, 2, 4};
        int k = 2;
        int[] result = new MaxSlidingWindow().maxSlidingWindow(nums, k);
        Assert.assertArrayEquals(result, new int[]{7, 4});
    }
}